This invention relates to cryptography and more particularly to applications of public key techniques for generating and modifying session keys for establishing and maintaining communication sessions.
In order to understand the invention, it is helpful to understand the context of the underlying basis of the invention and its place in the field of cryptography. Cryptography is the technology of applying an efficient, bijective transformation on sensitive information (the “plaintext”) to generate an equivalent but unintelligible representation of the same information (the “ciphertext”) using a well-specified procedure or recipe (the “encryption algorithm”). Such a transformation should have a number of properties:
1. It should be parameterized by a relatively small piece of information (the key material).
2. Given the key material, the transformation from plaintext to ciphertext or vice versa should be efficient.
3. The problem of determining the plaintext from the ciphertext without the key is believed to be difficult, as herein defined.
The efficiency or difficulty of a problem is determined by the resources required for a well-specified computational procedure to complete a processing task. Except in singular cases, the time required for the processing is the resource that is considered for determining efficiency.
For the same given problem (e.g. to add up n numbers), it is clear that the size of the input determines the resources required. Summing 10 numbers is clearly faster than summing 1000 numbers. A problem admits an efficient solution if there exists an algorithm for solving the problem that has a running time that grows as a polynomial of the size of the input data. A problem is difficult if it can be shown that there does not exist an efficient algorithm for the problem. In more practical terms, a problem is difficult if all algorithms that solve the problem take time greater than a polynomial.
To date, no one has been able to show conclusively that any reasonable problem is “difficult.” Mathematicians have therefore been able to formalize a related notion that is almost as powerful: There is a large group of problems for which the research community has not be able to find efficient algorithms. These problems are referred to as the NP-Complete problems. It is possible to show equivalence among these problems such that if anyone finds an efficient algorithm for any one of these problems, some simple machinery can be invoked to derive efficient algorithms for all the problems in the group. Since no solution to any problem in this class has been found to date, all problems in this group are believed to be difficult.
The notions of “efficient” and “difficult” are crucial to cryptography. The aim is to employ algorithms that would encrypt plaintext and decrypt ciphertext efficiently given the key in such a way that the problem of determining the plaintext from the ciphertext without knowledge the keys is believed to be difficult.
A cryptographic algorithm is considered “secure” if the problem of determining plaintext from the ciphertext is “believed to be difficult.”
In the field of cryptography, a particular class of functions usually derived from NP-Complete problems is used as a tool. These functions are the so-called one-way functions.
A one-way function f(x) has the property that given x, computing f(x) is efficient. However, given y, the problem of finding x such that f(x)=y is believed to be difficult. One-way functions have been used in authentication protocols like SKEY (“Applied Cryptography, Second Edition”, Bruce Schneier, Wiley, 1996, page 53).
Keys are used to encrypt and decrypt messages. Keys are exchanged or otherwise generated and made available to parties to a communication. If two parties wish to change keys for each message, and do not want to retain and manage a large bank of keys, it is possible to apply a one-way function to generate a progression of keys, that is, the keys for message n+1 can be generated from the key for message n.
If in addition, the generation of key n+1 is accompanied by the destruction of key n, then all messages Δn are protected even if key n+1 is compromised, since deriving key n from key n+1 would mean attempting to attack or go against a one-way function, which something that is known or otherwise assumed to be difficult. This is referred to in the literature as “Key Updating” (“Applied Cryptography, Second Edition”, Bruce Schneier, Wiley 1996, page 180).
While communication between two parties can be effected by typical key exchange and key updating techniques, a problem arises where multiple members of a group want to communicate securely. A conventional technique is to provide a separate key for each pair of communicants. However, if it is expedient to maintain a single key for the group and there is a desire to implement key updating, then the technology and protocol of key updating must be extended to the multiparty key updating case.
Consider a change in communication so that communication is only between two members of a group. As a result of the unique two-way communication, each must update their keys according to a common synchronization schedule which forces them to separate from the group. At the conclusion of their communication they will then be out of synchronization with the other members of the group who have not communicated and therefore have not updated their keys. One solution would be to broadcast a message to inform every member to update his/her keys. However, this is not an efficient solution. It would be wasteful of bandwidth, a valuable resource. What's more, some members may not be in communications with other members of the group and so they would not receive the message to update keys, with obvious security implications.
Known cryptographic trapdoor techniques are also vulnerable to the person-in-the-middle attack. Consider the example of two parties, Alice and Bob attempting to establish a secure communications channel, while an adversary, Mallory, can eavesdrop and modify the communicated information en route. What is needed is a mechanism to address this deficiency